This invention relates generally to binary counters and more particularly, it relates to an improved fast counter which is formed of uniform delay structures having a plurality of substantially identical bit cells so that each bit cell thereof has approximately the same amount of delay regardless of the order of the bit cell.
As is generally well known in the art, one of the most common ways to synchronize events occurring in digital data processing equipment is achieved by utilizing conventional binary counter circuits. These binary counter circuits are typically adapted to count up to a certain number of clock pulses. Further, such binary counter circuits are commonly operated on a straight binary counting code. A typical binary counter circuit consists of several stages connected in cascade each having a one-digit storage device. The successive count pulses are applied to the first stage or least significant bit storage device. The incoming pulses alternately set the first stage to "1" and then resets it to "0." On each reset pulse, the first stage sends a carry signal to the next stage or higher significant bit storage device. As a result, the second stage alternates between "0" and "1" each second input pulse and also transmits a carry signal to the next stage every time it resets to zero (i.e., every fourth input pulse), and so on for the remaining successive stages.
This kind of binary counter is sometimes referred to as a ripple carry counter. As is apparent to those skilled in the art, each counter stage requires a certain amount of time in order to change state and thus a considerable amount of propagation delay will occur before the final stage or most significant bit receives its carry signal. This is especially true when there are more than just a few stages involved. For example, in a 32-bit binary counter this propagation delay may be in the order of several microseconds.
As is also well known among counter designers, there always exists a trade-off in the amount of chip area used and the propagation delay. If the clock speeds are slow enough, the ripple carry-type counters would be quite adequate to provide a low cost solution utilizing less chip space. However, the speed of the carry propagation delay becomes an important design factor when dealing with counters used in high speed digital applications.
Various type of circuit arrangements, such as "carry-look ahead" schemes, have been employed heretofore in an attempt to improve the carry speed. In such "carry-look ahead" schemes, "propagate" and "generate" terms are typically evaluated for each bit cell so as to perform the carry-look ahead function for each cell and then the next state of the bit is evaluated. However, a severe disadvantage of these schemes is that as the number of stages increases the number of logic gates necessary to produce the "propagate" and "generate" terms, which are subsequently used to produce the outputs of the counter bit cells, is substantially increased. As a result, the need of increased amounts of chip area for such logic gates renders this approach to be extremely costly in manufacturing and use.
The inventor has discovered a new technique for designing a fast counter by realizing the function of the counting operation in the binary code pattern. For a straight 5-bit up-counter, as illustrated in the Table listed below, the code pattern for the first eight counts (0-7) and a corresponding bit-flip map derived therefrom are shown:
TABLE ______________________________________ Row Bit-Flip Map Counter Output ______________________________________ 1 00001 00000 2 00011 00001 3 00001 00010 4 00111 00011 5 00001 00100 6 00011 00101 7 00001 00110 8 01111 00111 . . 01000 . . . . . . ______________________________________
The bit-flip map is derived by referring to the current counter output and the next counter output. As can be seen from row 1 and row 2, the counter output is changed from "00000" to "00001" which means that only the least significant bit (LSB) was flipped in-going to the next state. Thus, row 1 of the bit-flip map is made to be "00001" indicating that only the least significant bit has to be flipped in going from row 1 to row 2 of the counter. From row 2 and row 3, the counter output is changed from "00001" to "00010" which means that the least significant bit and the next higher bit were flipped in going to the next state. Thus, row 2 of the bit-flip map is made to be "00011" indicating that only the two LSB have to be flipped in going from row 2 to row 3 of the counter. This process can be repeated again and again so as to generate the corresponding bit-flip map.
It can be observed from the bit-flip map in the Table above that by beginning from the LSB position in the bit-flip map once a value of "0" is reached all the next higher bit positions will also have values of "0." For example, in row 4 corresponding to count 4 (00111) the three LSB in the bit-flip map are all "1's", and the fourth LSB is at "0." This means that all of the bits higher than the fourth LSB will also be "0's." As a result, on the next count operation (count 5), only the first three positions beginning from the LSB in the counter output will be flipped or changed. By utilizing this technique developed by the inventor, all of the remaining next states of the counter outputs can be derived from the bit-flip map. As a consequence, an improved fast counter can be implemented so as to achieve a minimum propagation delay at relatively low cost.